package leetcode.linked;

/**
 * 反转链表 简单
 */
public class Solution206反转链表 extends ListNode {
    // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
    // 反转 1 <-- 2 <-- 3 <-- 4 <-- 5

    public ListNode reverseListRecursion(ListNode head) {

        // 寻找递归终止条件
        // 1、head 指向的结点为 null
        // 2、head 指向的结点的下一个结点为 null
        // 在这两种情况下，反转之后的结果还是它自己本身
        if (head == null || head.next == null) {
            return head;
        }

        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        ListNode cur = reverseListRecursion(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 反转 1 <-- 2 <-- 3 <-- 4 <-- 5
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;


        // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 创建 2 个变量分别表示前一个节点，和后一个节点
        ListNode prev = null, tmp = null;
        //1 --> 2 --> 3 --> 4 --> 5
        //5 --> 4 --> 3 --> 2 --> 1
        while (head != null) {
            // 记录后一个节点，避免信息丢失
            tmp = head.next;

            // 反转：使当前 next 指针之前之前的节点
            head.next = prev;

            // 为接下来的操作作准备：移动前一个指针到当前
            prev = head;

            // 为接下来的操作作准备：移动当前指针到后一个
            head = tmp;
        }

        // 返回反转后的链表
        return prev;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);

        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;

        listNode2.next = new ListNode(3, null);


        Solution206反转链表 solution206 = new Solution206反转链表();
        solution206.reverseListRecursion(listNode1);
//        solution206.reverseList(listNode1);
    }
}
